Transformación polinomial
- Transformación polinomial
- En teoría de la complejidad computacional, una Transformación polinomial (también conocida como una reducción de Karp) es una forma de reducir un problema de decisión en otro de forma que cualquier algoritmo que resuelva el primer problema produzca inmediatamente una solución al segundo, por un costo polinomial (cuando el problema transformado es suficientemente complejo, este costo resulta despreciable en el cálculo del costo total del problema).
Enciclopedia Universal.
2012.
Mira otros diccionarios:
Transformación polinómica — En complejidad computacional, una transformación polinomial, reducción polinomial o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza… … Wikipedia Español
EXPTIME — En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una… … Wikipedia Español
EXPSPACE — Saltar a navegación, búsqueda En teoría de la complejidad computacional, la clase de complejidad EXPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2p(n)), donde p(n)… … Wikipedia Español
Distribución normal — Saltar a navegación, búsqueda Distribución normal Función de densidad de probabilidad La línea verde corresponde a la distribución normal estandar Función de distribución de probabilidad … Wikipedia Español
Regresión no lineal — Saltar a navegación, búsqueda En estadística, la regresión no lineal es un problema de inferencia para un modelo tipo: basado en datos multidimensionales x,y, donde f es alguna función no lineal respecto a algunos parámetros desconocidos θ. Como… … Wikipedia Español
Espacio vectorial — Saltar a navegación, búsqueda Un espacio vectorial es un conjunto de objetos (llamados vectores) que pueden escalarse y sumarse. Un espacio vectorial (o espacio lineal) es el objeto básico de estudio en la rama de la matemática llamada álgebra… … Wikipedia Español
Gramática libre de contexto — En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no… … Wikipedia Español
LFSR — significa linear feedback shift register, que se traduce como: registro de desplazamiento con retroalimentación lineal. Es un registro de desplazamiento en el cual la entrada es un bit proveniente de aplicar una función de transformación lineal a … Wikipedia Español
NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… … Wikipedia Español
